package com.leetCode.tree;

import java.util.*;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-27 11:52:36
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-27     张李鑫                     1.0         1.0 Version
 */
public class LevelOrder {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        ArrayList<List<Integer>> lists = new ArrayList<>();
        ArrayList<Integer> child = new ArrayList<>();
        lists.add(child);

        Queue<TreeNode> stack = new LinkedList<>();
        TreeNode end = root;
        TreeNode nextEnd = null;
        stack.add(root);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.poll();
            child.add(pop.val);

            if (pop.left != null) {
                stack.add(pop.left);
                nextEnd = pop.left;
            }

            if (pop.right != null) {
                stack.add(pop.right);
                nextEnd = pop.right;
            }
            if (end == pop&&!stack.isEmpty()) {
                child = new ArrayList<>();
                lists.add(child);
                end = nextEnd;
            }
        }
        return lists;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3);
        TreeNode treeNode1 = new TreeNode(9);
        TreeNode treeNode2 = new TreeNode(20);
        TreeNode treeNode3 = new TreeNode(15);
        TreeNode treeNode4 = new TreeNode(7);

        treeNode.left = treeNode1;
        treeNode.right = treeNode2;

        treeNode2.left = treeNode3;
        treeNode2.right = treeNode4;
        System.out.println(levelOrder(treeNode));

    }

}
